Search results for "Kolakoski word"
showing 3 items of 3 documents
Automata and differentiable words
2011
We exhibit the construction of a deterministic automaton that, given k > 0, recognizes the (regular) language of k-differentiable words. Our approach follows a scheme of Crochemore et al. based on minimal forbidden words. We extend this construction to the case of C\infinity-words, i.e., words differentiable arbitrary many times. We thus obtain an infinite automaton for representing the set of C\infinity-words. We derive a classification of C\infinity-words induced by the structure of the automaton. Then, we introduce a new framework for dealing with \infinity-words, based on a three letter alphabet. This allows us to define a compacted version of the automaton, that we use to prove that ev…
Vertical Representation of C∞-words
2015
International audience; We present a new framework for dealing with C∞-words, based on their left and right frontiers. Thisallows us to give a compact representation of them, and to describe the set of C∞-words throughan infinite directed acyclic graph G. This graph is defined by a map acting on the frontiers ofC∞-words. We show that this map can be defined recursively and with no explicit reference toC∞-words. We then show that some important conjectures on C∞-words follow from analogousstatements on the structure of the graph G.
Some Remarks on Differentiable Sequences and Recursivity
2010
International audience; We investigate the recursive structure of differentiable sequences over the alphabet {1, 2}. We derive a recursive formula for the (n + 1)-th symbol of a differentiable sequence, which yields to a new recursive formula for the Kolakoski sequence. Finally, we show that the sequence of absolute differences of consecutive symbols of a differentiable sequence u is a morphic image of the run-length encoding of u.